# 第4节擒贼先擒王--并查集
# 靠左原则，擒贼先擒王
f = [0 for i in range(0, 101)]
n, m, k, s = 0, 0, 0, 0


# 初始化
def init():
    for i in range(1, n + 1):
        f[i] = i


# 擒贼先擒王的递归
def get_f(v):
    if v == f[v]:
        return v
    else:
        # 这里是路径压缩，每次在函数返回的时候。顺带把路上遇到的人的“BOSs”改为最后找
        # 到的祖宗编号，也就是犯罪团伙的最高领导人编号。这样可以提高今后找到犯罪团伙的
        # 最高领导人（其实就是树的祖先）的速度。
        f[v] = get_f(f[v])
        return f[v]


# 合并两个子集的函数
def merge(v: int, u: int):
    t1 = get_f(v)
    t2 = get_f(u)
    if t1 != t2:
        f[t2] = t1
        # “靠左”原则，左边变成右边的BOSs。即把右边的集合，作为左边集合的子集合
        # 经过路径压缩以后，将f[u]的根的值也赋值为v的祖先f[t1]


# main函数
if __name__ == '__main__':
    n = 10  # 强盗人数
    m = 9  # 线索数量
    init()
    # 线索
    e = [[1, 2], [3, 4], [5, 2], [4, 6], [2, 6], [8, 7], [9, 7], [1, 6], [2, 4]]
    for k in e:
        merge(k[0], k[1])

    # 扫描有多少个独立的团伙
    for i in range(1, n + 1):
        if i == f[i]:
            s += 1
    print(f)
    print('%d' % s)
